0704. 二分查找【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法（线性扫描）
• 3. 🎯 s.2 - 二分查找
• 4. 🎯 s.3 - 使用原生 API

1. 📝 题目描述

• leetcode

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

---

示例 1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

---

示例 2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

2. 🎯 s.1 - 暴力解法（线性扫描）

1.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i
    if (nums[i] > target) return -1
  }
  return -1
}

• 时间复杂度：$O(n)$，最坏情况下遍历整个数组
• 空间复杂度：$O(1)$，仅使用常量额外变量

算法思路：

• 从左到右逐个比较元素与 target
• 因为数组有序，若遇到元素大于 target 可提前返回 -1

3. 🎯 s.2 - 二分查找

1.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0,
    r = nums.length - 1,
    mid = ((r - l) >> 1) + l
  while (l <= r) {
    if (nums[mid] === target) return mid
    else if (nums[mid] < target) l = mid + 1
    else r = mid - 1
    mid = ((r - l) >> 1) + l
  }
  return -1
}

• 时间复杂度：$O(\log n)$，每次将搜索区间减半
• 空间复杂度：$O(1)$，只用常量变量维护边界与中点

算法思路：

• 维护左右边界 l、r，每轮计算中点 mid
• 根据 nums[mid] 与 target 比较，缩小到左半区或右半区
• 找到则返回索引，区间无元素则返回 -1

4. 🎯 s.3 - 使用原生 API

1.js

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  return nums.indexOf(target)
}

• 时间复杂度：$O(n)$，indexOf 为线性查找
• 空间复杂度：$O(1)$

算法思路：

• 直接利用语言内置的查找接口